from typing import *


class Solution:
    def countPaths(self, n: int, edges: List[List[int]]) -> int:

        def prime(n):
            h = [True] * (n + 1)
            h[0] = h[1] = False
            primes = []
            for i in range(2, n + 1):
                if h[i]:
                    primes.append(i)
                for p in primes:
                    if i * p > n:
                        break
                    h[i * p] = False
                    if i % p == 0:
                        break
            return h

        isPrime = prime(n)

        dp = [[] for _ in range(n + 1)]
        nexts = [[] for _ in range(n + 1)]
        for a, b in edges:
            nexts[a].append(b)
            nexts[b].append(a)

        def dfs(root, parent):
            a = 0 if isPrime[root] else 1
            b = a ^ 1
            for nxt in nexts[root]:
                if nxt != parent:
                    i, j = dfs(nxt, root)
                    if isPrime[root]:
                        b += i
                    else:
                        a += i
                        b += j
            dp[root] = [a, b]
            return a, b

        dfs(1, -1)

        ans = 0

        def dfs2(root, parent):
            nonlocal ans
            ans += dp[root][1]
            if isPrime[root]:
                ans -= 1
            for nxt in nexts[root]:
                if nxt != parent:
                    a, b = dp[root]
                    c, d = dp[nxt]

                    if isPrime[root]:
                        dp[root][1] -= c
                    else:
                        dp[root][0] -= c
                        dp[root][1] -= d

                    if isPrime[nxt]:
                        dp[nxt][1] += dp[root][0]
                    else:
                        dp[nxt][0] += dp[root][0]
                        dp[nxt][1] += dp[root][1]

                    dfs2(nxt, root)
                    dp[root] = [a, b]
                    dp[nxt] = [c, d]

        dfs2(1, -1)
        return ans // 2
